﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;
using System.IO;

namespace WindowsFormsApp1
{
    public partial class FormSudoku : Form
    {
        // 定义Cell结构体，用于替代Tuple<int, int>，提高代码可读性
        public struct Cell
        {
            public int Row { get; }
            public int Col { get; }

            public Cell(int row, int col)
            {
                Row = row;
                Col = col;
            }

            // 为了支持HashSet.Contains方法，需要重写Equals和GetHashCode
            public override bool Equals(object obj)
            {
                if (obj is Cell other)
                {
                    return Row == other.Row && Col == other.Col;
                }
                return false;
            }

            public override int GetHashCode()
            {
                return (Row, Col).GetHashCode();
            }
        }

        // 定义常量表示数独大小
        private const int SudokuSize = 9;

        public FormSudoku()
        {
            InitializeComponent();            
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            dataGridView1.AllowUserToAddRows = false;
            dataGridView1.AllowUserToDeleteRows = false;
            dataGridView1.AllowUserToResizeColumns = false;
            dataGridView1.AllowUserToResizeRows = false;
            dataGridView1.ColumnHeadersHeightSizeMode = System.Windows.Forms.DataGridViewColumnHeadersHeightSizeMode.AutoSize;
            dataGridView1.ColumnHeadersVisible = false;
            dataGridView1.RowHeadersVisible = false;
            dataGridView1.RowHeadersWidth = 49;
            dataGridView1.RowTemplate.Height = 25;
            
            // 设置简单难度为默认选中
            radioButton1.Checked = true;

            InitialDataGridView();

        }

        private void buttonNew_Click(object sender, EventArgs e)
        {            // 生成有效的数独解决方案
            int[,] sudokuArray = GenerateValidSudoku();
            
            // 创建一个副本用于生成题目
            int[,] puzzleArray = new int[SudokuSize, SudokuSize];
            Array.Copy(sudokuArray, puzzleArray, sudokuArray.Length);

            // 配置dataGridView1以显示9x9数组
            InitialDataGridView();

            // 根据选中的难度级别确定目标隐藏比例
            int targetHidePercentage = 40; // 默认简单难度
            if (radioButton2.Checked) // 中等难度
                targetHidePercentage = 50;
            else if (radioButton3.Checked) // 困难难度
                targetHidePercentage = 60;

            // 生成唯一解的数独题目
            GenerateUniqueSolutionPuzzle(puzzleArray, targetHidePercentage);

            // 将数组数据显示到dataGridView1
            for (int i = 0; i < SudokuSize; i++)
            {
                for (int j = 0; j < SudokuSize; j++)
                {
                    if (puzzleArray[i, j] == 0)
                    {
                        dataGridView1.Rows[i].Cells[j].Value = null;
                    }
                    else
                    {
                        dataGridView1.Rows[i].Cells[j].Value = puzzleArray[i, j];
                    }
                }
            }

            // 检查数独规则
            CheckSudokuRules();
        }

        // 生成唯一解的数独题目
        private void GenerateUniqueSolutionPuzzle(int[,] grid, int targetHidePercentage)
        {
            Random random = new Random();
            int totalCells = SudokuSize * SudokuSize;
            int targetHiddenCells = (int)(totalCells * targetHidePercentage / 100.0);
            int currentHiddenCells = 0;

            // 创建单元格位置列表并随机排序
            List<Cell> cells = new List<Cell>();
            for (int i = 0; i < SudokuSize; i++)
            {
                for (int j = 0; j < SudokuSize; j++)
                {
                    cells.Add(new Cell(i, j));
                }
            }

            // 随机打乱单元格顺序
            for (int i = 0; i < cells.Count; i++)
            {
                int j = random.Next(i, cells.Count);
                Cell temp = cells[i];
                cells[i] = cells[j];
                cells[j] = temp;
            }

            // 尝试隐藏数字，同时确保答案唯一性
            foreach (var cell in cells)
            {
                if (currentHiddenCells >= targetHiddenCells)
                    break;

                int row = cell.Row;
                int col = cell.Col;
                int originalValue = grid[row, col];

                // 暂时隐藏该数字
                grid[row, col] = 0;

                // 检查是否仍有唯一解
                if (HasUniqueSolution(grid))
                {
                    // 如果仍有唯一解，保留隐藏状态
                    currentHiddenCells++;
                }
                else
                {
                    // 如果解不唯一，恢复原始值
                    grid[row, col] = originalValue;
                }
            }
        }

        // 检查数独是否有唯一解
        private bool HasUniqueSolution(int[,] grid)
        {
            // 在方法内部创建副本，避免每次调用都在外部创建副本
            int[,] gridCopy = new int[SudokuSize, SudokuSize];
            for (int i = 0; i < SudokuSize; i++)
            {
                for (int j = 0; j < SudokuSize; j++)
                {
                    gridCopy[i, j] = grid[i, j];
                }
            }
            
            int solutionCount = 0;
            CountSolutions(gridCopy, ref solutionCount);
            return solutionCount == 1;
        }

        // 计算数独解的数量（限制在2个个以内以提高效率）
        private bool CountSolutions(int[,] grid, ref int solutionCount)
        {
            // 快速检查是否已经找到超过1个解，提前剪枝
            if (solutionCount >= 2)
                return true;

            // 找到一个空单元格
            int row = -1, col = -1;
            bool isEmpty = false;
            for (int i = 0; i < SudokuSize; i++)
            {
                for (int j = 0; j < SudokuSize; j++)
                {
                    if (grid[i, j] == 0)
                    {
                        row = i;
                        col = j;
                        isEmpty = true;
                        break;
                    }
                }
                if (isEmpty)
                    break;
            }

            // 如果没有空单元格，说明找到了一个解
            if (!isEmpty)
            {
                solutionCount++;
                // 一旦找到2个解，立即返回true以终止所有递归
                return solutionCount >= 2;
            }

            // 尝试在空单元格中填入1-9
            for (int num = 1; num <= SudokuSize; num++)
            {
                if (IsValid(grid, row, col, num))
                {
                    grid[row, col] = num;

                    // 递归求解，如果找到2个或更多解，立即终止
                    if (CountSolutions(grid, ref solutionCount))
                        return true;

                    // 回溯
                    grid[row, col] = 0;
                }
            }

            return false;
        }

        // 生成有效的数独解决方案
        private int[,] GenerateValidSudoku()
        {
            int[,] grid = new int[SudokuSize, SudokuSize];
            Random random = new Random();

            // 填充对角线上的3x3区块（这些区块不互相影响）
            for (int block = 0; block < SudokuSize; block += 3)
            {
                FillBlock(grid, block, block, random);
            }

            // 使用回溯算法填充剩余的格子（带随机顺序）
            SolveSudoku(grid, random);

            return grid;
        }

        // 填充3x3区块
        private void FillBlock(int[,] grid, int row, int col, Random random)
        {
            List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            Shuffle(numbers, random);

            // 填充到3x3区块
            int index = 0;
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    grid[row + i, col + j] = numbers[index++];
                }
            }
        }

        // 数独求解的回溯算法（带随机顺序）
        private bool SolveSudoku(int[,] grid, Random random = null)
        {
            // 如果没有提供随机数生成器，创建一个新的
            bool useRandomOrder = random != null;
            Random localRandom = random ?? new Random();

            for (int row = 0; row < SudokuSize; row++)
            {
                for (int col = 0; col < SudokuSize; col++)
                {
                    // 找到一个空格
                    if (grid[row, col] == 0)
                    {
                        // 准备要尝试的数字列表
                        List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
                        
                        // 如果需要随机顺序，打乱数字列表
                        if (useRandomOrder)
                        {
                            Shuffle(numbers, localRandom);
                        }

                        // 尝试填入数字
                        foreach (int num in numbers)
                        {
                            if (IsValid(grid, row, col, num))
                            {
                                grid[row, col] = num;

                                // 递归求解
                                if (SolveSudoku(grid, localRandom))
                                    return true;

                                // 回溯
                                grid[row, col] = 0;
                            }
                        }
                        return false; // 当前格子无法填入任何数字，回溯
                    }
                }
            }
            return true; // 所有格子都已填满，求解成功
        }

        // 打乱列表顺序的辅助方法
        private void Shuffle<T>(List<T> list, Random random)
        {
            for (int i = 0; i < list.Count; i++)
            {
                int j = random.Next(i, list.Count);
                T temp = list[i];
                list[i] = list[j];
                list[j] = temp;
            }
        }

        private void buttonLoad_Click(object sender, EventArgs e)
        {
            // 创建OpenFileDialog用于选择CSV文件
            using (OpenFileDialog openFileDialog = new OpenFileDialog())
            {
                openFileDialog.Filter = "数据文件 (*.txt)|*.txt|所有文件 (*.*)|*.*";
                openFileDialog.Title = "选择数据文件";

                if (openFileDialog.ShowDialog() == DialogResult.OK)
                {
                    try
                    {                       
                        // 读取CSV文件内容
                        string[] lines = File.ReadAllLines(openFileDialog.FileName);

                        // 配置dataGridView1为固定9x9
                        InitialDataGridView();

                        // 填充数据，只处理最多9行9列
                        for (int i = 0; i < Math.Min(SudokuSize, lines.Length); i++)
                        {
                            string[] values = lines[i].Split(',');
                            for (int j = 0; j < Math.Min(SudokuSize, values.Length); j++)
                            {                                
                                // 尝试转换为整数，只接受数字
                                if (int.TryParse(values[j].Trim(), out int num))
                                {
                                    dataGridView1.Rows[i].Cells[j].Value = num;
                                }
                            }
                        }

                        // 检查数独规则
                        CheckSudokuRules();

                        //MessageBox.Show("数据文件加载成功！", "成功", MessageBoxButtons.OK, MessageBoxIcon.Information);
                    }
                    catch (Exception ex)
                    {
                        MessageBox.Show("加载数据文件时出错: " + ex.Message, "错误", MessageBoxButtons.OK, MessageBoxIcon.Error);
                    }
                }
            }
        }

        private void buttonSave_Click(object sender, EventArgs e)
        {
            // 创建SaveFileDialog用于保存CSV文件
            using (SaveFileDialog saveFileDialog = new SaveFileDialog())
            {
                saveFileDialog.Filter = "数据文件 (*.txt)|*.txt";
                saveFileDialog.Title = "保存数据文件";
                saveFileDialog.DefaultExt = "txt";

                if (saveFileDialog.ShowDialog() == DialogResult.OK)
                {
                    try
                    {
                        // 创建一个StringBuilder来存储CSV内容
                        System.Text.StringBuilder csvContent = new System.Text.StringBuilder();

                        // 遍历9x9网格
                        for (int i = 0; i < SudokuSize; i++)
                        {
                            string[] rowValues = new string[SudokuSize];

                            for (int j = 0; j < SudokuSize; j++)
                            {                                // 获取单元格值，默认为空
                                rowValues[j] = dataGridView1.Rows[i].Cells[j].Value?.ToString() ?? " ";
                            }

                            // 将行添加到CSV内容
                            csvContent.AppendLine(string.Join(",", rowValues));
                        }

                        // 写入文件
                        File.WriteAllText(saveFileDialog.FileName, csvContent.ToString(), System.Text.Encoding.UTF8);

                        MessageBox.Show("数据文件保存成功！", "成功", MessageBoxButtons.OK, MessageBoxIcon.Information);
                    }
                    catch (Exception ex)
                    {
                        MessageBox.Show("保存数据文件时出错: " + ex.Message, "错误", MessageBoxButtons.OK, MessageBoxIcon.Error);
                    }
                }
            }
        }

        // 检查数独规则，将违反规则的数字标记为红色加粗
        private void CheckSudokuRules()
        {
            // 获取当前表格中的数字
            int?[,] grid = new int?[SudokuSize, SudokuSize];
            for (int i = 0; i < SudokuSize; i++)
            {
                for (int j = 0; j < SudokuSize; j++)
                {
                    if (dataGridView1.Rows[i].Cells[j].Value != null && int.TryParse(dataGridView1.Rows[i].Cells[j].Value.ToString(), out int value))
                    {
                        grid[i, j] = value;
                    }
                }
            }

            // 创建违反规则的单元格集合
            HashSet<Cell> invalidCells = new HashSet<Cell>();

            // 检查数字有效性并收集行、列、区块中的重复数字
            CheckNumberValidity(grid, invalidCells);
            CheckRowsForDuplicates(grid, invalidCells);
            CheckColumnsForDuplicates(grid, invalidCells);
            CheckBlocksForDuplicates(grid, invalidCells);

            // 应用样式到所有单元格
            foreach (DataGridViewRow row in dataGridView1.Rows)
            {
                foreach (DataGridViewCell cell in row.Cells)
                {
                    // 重置单元格样式
                    cell.Style.Font = new Font(dataGridView1.Font, FontStyle.Regular);
                    cell.Style.BackColor = GetSudokuBlockBackgroundColor(cell.RowIndex, cell.ColumnIndex);
                    cell.Style.ForeColor = Color.Black;

                    // 检查单元格是否违反规则
                    if (invalidCells.Contains(new Cell(cell.RowIndex, cell.ColumnIndex)))
                    {
                        cell.Style.BackColor = Color.Red;
                        cell.Style.ForeColor = Color.Yellow;
                        cell.Style.Font = new Font(dataGridView1.Font, FontStyle.Bold);
                    }
                }
            }
        }

        // 检查数字是否在1-9范围内
        private void CheckNumberValidity(int?[,] grid, HashSet<Cell> invalidCells)
        {
            for (int i = 0; i < SudokuSize; i++)
            {
                for (int j = 0; j < SudokuSize; j++)
                {
                    if (grid[i, j].HasValue)
                    {
                        int value = grid[i, j].Value;
                        if (value < 1 || value > 9)
                        {
                            invalidCells.Add(new Cell(i, j));
                        }
                    }
                }
            }
        }

        // 检查行中是否有重复数字
        private void CheckRowsForDuplicates(int?[,] grid, HashSet<Cell> invalidCells)
        {
            for (int i = 0; i < SudokuSize; i++)
            {
                HashSet<int> seen = new HashSet<int>();
                for (int j = 0; j < SudokuSize; j++)
                {
                    if (grid[i, j].HasValue)
                    {
                        int value = grid[i, j].Value;
                        if (value >= 1 && value <= 9 && !seen.Add(value))
                        {
                            invalidCells.Add(new Cell(i, j));
                        }
                    }
                }
            }
        }

        // 检查列中是否有重复数字
        private void CheckColumnsForDuplicates(int?[,] grid, HashSet<Cell> invalidCells)
        {
            for (int j = 0; j < SudokuSize; j++)
            {
                HashSet<int> seen = new HashSet<int>();
                for (int i = 0; i < SudokuSize; i++)
                {
                    if (grid[i, j].HasValue)
                    {
                        int value = grid[i, j].Value;
                        if (value >= 1 && value <= 9 && !seen.Add(value))
                        {
                            invalidCells.Add(new Cell(i, j));
                        }
                    }
                }
            }
        }

        // 检查3x3区块中是否有重复数字
        private void CheckBlocksForDuplicates(int?[,] grid, HashSet<Cell> invalidCells)
        {
            for (int blockRow = 0; blockRow < 3; blockRow++)
            {
                for (int blockCol = 0; blockCol < 3; blockCol++)
                {
                    // 获取区块的起始位置
                    int startRow = blockRow * 3;
                    int startCol = blockCol * 3;

                    HashSet<int> seen = new HashSet<int>();
                    // 遍历区块内的所有单元格
                    for (int i = 0; i < 3; i++)
                    {
                        for (int j = 0; j < 3; j++)
                        {
                            int row = startRow + i;
                            int col = startCol + j;

                            if (grid[row, col].HasValue)
                            {
                                int value = grid[row, col].Value;
                                if (value >= 1 && value <= 9 && !seen.Add(value))
                                {
                                    invalidCells.Add(new Cell(row, col));
                                }
                            }
                        }
                    }
                }
            }
        }

        // 统一配置DataGridView为9x9格式的方法
        private void InitialDataGridView()
        {
            // 清空现有内容
            dataGridView1.Rows.Clear();
            dataGridView1.Columns.Clear();

            // 设置DataGridView的AutoSizeColumnsMode为Fill，使各列平均分布
            dataGridView1.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.Fill;

            // 设置字体大小更大
            dataGridView1.Font = new Font("Tahoma", 13, FontStyle.Bold);

            // 设置为固定的9列9行
            dataGridView1.ColumnCount = SudokuSize;
            dataGridView1.RowCount = SudokuSize;

            // 设置列标题和宽度
            for (int i = 0; i < SudokuSize; i++)
            {
                // 设置单元格文字居中
                dataGridView1.Columns[i].DefaultCellStyle.Alignment = DataGridViewContentAlignment.MiddleCenter;
            }

            // 设置行标题和高度
            for (int i = 0; i < SudokuSize; i++)
            {
                dataGridView1.Rows[i].Height = 42; 
            }

            // 按照数独9宫格设置交替背景色
            foreach (DataGridViewRow row in dataGridView1.Rows)
            {
                foreach (DataGridViewCell cell in row.Cells)
                {
                    // 使用GetSudokuBlockBackgroundColor方法计算背景色
                    cell.Style.BackColor = GetSudokuBlockBackgroundColor(cell.RowIndex, cell.ColumnIndex);
                    // 重置字体和颜色样式
                    cell.Style.ForeColor = Color.Black;
                    cell.Style.Font = new Font(dataGridView1.Font, FontStyle.Regular);
                }
            }
            
            // 取消默认选中状态，确保没有单元格被默认选中
            dataGridView1.ClearSelection();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            CheckSudokuRules();
        }

        private void buttonSolve_Click(object sender, EventArgs e)
        {
            // 从DataGridView读取当前数独状态
            int[,] grid = new int[SudokuSize, SudokuSize];
            bool[,] isFixed = new bool[SudokuSize, SudokuSize];

            for (int row = 0; row < SudokuSize; row++)
            {
                for (int col = 0; col < SudokuSize; col++)
                {
                    if (dataGridView1.Rows[row].Cells[col].Value != null &&
                        int.TryParse(dataGridView1.Rows[row].Cells[col].Value.ToString(), out int value))
                    {
                        grid[row, col] = value;
                        isFixed[row, col] = true; // 标记原始存在的数字为固定，避免被修改
                    }
                    else
                    {
                        grid[row, col] = 0; // 0表示空格
                        isFixed[row, col] = false;
                    }
                }
            }

            // 尝试求解数独
            if (SolveSudoku(grid))
            {
                // 求解成功，将结果填充回DataGridView
                for (int row = 0; row < SudokuSize; row++)
                {
                    for (int col = 0; col < SudokuSize; col++)
                    {
                        // 只填充空白单元格，保留原始数字
                        if (!isFixed[row, col] && grid[row, col] != 0)
                        {
                            dataGridView1.Rows[row].Cells[col].Value = grid[row, col].ToString();
                            // 为填充的数字设置不同的样式以示区分
                            dataGridView1.Rows[row].Cells[col].Style.BackColor = Color.LightBlue;
                        }
                    }
                }
                // 检查是否还有违反规则的情况
                CheckSudokuRules();
            }
            else
            {
                MessageBox.Show("无法求解当前数独，请检查输入是否正确。");
            }
        }

        // 数独求解的回溯算法
        private bool SolveSudoku(int[,] grid)
        {
            for (int row = 0; row < SudokuSize; row++)
            {
                for (int col = 0; col < SudokuSize; col++)
                {
                    // 找到一个空格
                    if (grid[row, col] == 0)
                    {
                        // 尝试填入1-9
                        for (int num = 1; num <= 9; num++)
                        {
                            if (IsValid(grid, row, col, num))
                            {
                                // 如果当前数字有效，填入并继续求解
                                grid[row, col] = num;

                                // 递归求解剩余部分
                                if (SolveSudoku(grid))
                                    return true;

                                // 如果后续无解，回溯
                                grid[row, col] = 0;
                            }
                        }
                        // 当前格子无法填入任何数字，回溯
                        return false;
                    }
                }
            }
            // 所有格子都已填满，求解成功
            return true;
        }

        // 检查在指定位置填入数字是否有效
        private bool IsValid(int[,] grid, int row, int col, int num)
        {
            // 检查行
            for (int x = 0; x < SudokuSize; x++)
            {
                if (grid[row, x] == num)
                    return false;
            }

            // 检查列
            for (int x = 0; x < SudokuSize; x++)
            {
                if (grid[x, col] == num)
                    return false;
            }

            // 检查3x3子网格
            int startRow = row - row % 3;
            int startCol = col - col % 3;

            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (grid[i + startRow, j + startCol] == num)
                        return false;
                }
            }

            return true;
        }

        private void buttonClear_Click(object sender, EventArgs e)
        {
            InitialDataGridView();
        }

        private void ResetCellStyles()
        {
            foreach (DataGridViewRow row in dataGridView1.Rows)
            {
                foreach (DataGridViewCell cell in row.Cells)
                {
                    // 重置为默认样式，但保持3x3区域的背景色交替
                    cell.Style.BackColor = GetSudokuBlockBackgroundColor(cell.RowIndex, cell.ColumnIndex);
                    cell.Style.ForeColor = Color.Black;
                }
            }
            
            dataGridView1.ClearSelection();
        }

        private Color GetSudokuBlockBackgroundColor(int row, int col)
        {
            // 计算单元格属于哪个3x3块
            int blockRow = row / 3;
            int blockCol = col / 3;
            
            // 相邻3x3块使用不同的背景色，创建棋盘格效果
            if ((blockRow + blockCol) % 2 == 0)
            {
                return Color.White; // 浅色背景
            }
            else
            {
                return Color.LightGray; // 稍深的背景色，用于区分3x3块
            }
        }

        private void HighlightRowAndColumn(int rowIndex, int columnIndex)
        {
            // 高亮整行
            foreach (DataGridViewCell cell in dataGridView1.Rows[rowIndex].Cells)
            {
                cell.Style.BackColor = Color.LightGreen;
            }

            // 高亮整列
            foreach (DataGridViewRow row in dataGridView1.Rows)
            {
                row.Cells[columnIndex].Style.BackColor = Color.LightGreen;
            }

            // 高亮选中的单元格（更明显）
            dataGridView1.Rows[rowIndex].Cells[columnIndex].Style.BackColor = Color.Green;
        }

        private void HighlightSameNumbers(int rowIndex, int columnIndex)
        {
            // 获取选中单元格的值
            object cellValue = dataGridView1.Rows[rowIndex].Cells[columnIndex].Value;
            if (cellValue != null && cellValue != DBNull.Value)
            {
                string targetValue = cellValue.ToString();
                if (!string.IsNullOrEmpty(targetValue))
                {
                    foreach (DataGridViewRow row in dataGridView1.Rows)
                    {
                        foreach (DataGridViewCell cell in row.Cells)
                        {
                            // 如果单元格有值且与选中单元格的值相同，且不是选中的行或列
                            if (cell.Value != null && cell.Value != DBNull.Value &&
                                cell.Value.ToString() == targetValue &&
                                cell.RowIndex != rowIndex && cell.ColumnIndex != columnIndex)
                            {
                                // 加深背景色显示
                                cell.Style.BackColor = SystemColors.Highlight;
                                cell.Style.ForeColor = SystemColors.HighlightText;
                            }
                        }
                    }
                }
            }
        }
         

        // 处理单元格高亮显示的通用方法
        private void HighlightCell(int rowIndex, int columnIndex)
        {
            if (rowIndex >= 0 && columnIndex >= 0)
            {
                // 高亮显示整行整列
                HighlightRowAndColumn(rowIndex, columnIndex);
                
                // 如果单元格有数字，高亮显示所有相同数字的单元格
                HighlightSameNumbers(rowIndex, columnIndex);
            }
        }

        
        private void dataGridView1_CellMouseEnter(object sender, DataGridViewCellEventArgs e)
        {
            // 使用通用方法高亮单元格
            HighlightCell(e.RowIndex, e.ColumnIndex);
        }

        private void dataGridView1_CellMouseLeave(object sender, DataGridViewCellEventArgs e)
        {
            // 重置所有单元格样式
            ResetCellStyles();
        }
    }
}

       
